/*
题目: 整数替换
给定一个正整数 n ，你可以做如下操作：

    如果 n 是偶数，则用 n / 2替换 n 。
    如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。

返回 n 变为 1 所需的 最小替换次数 。

https://leetcode.cn/problems/integer-replacement/
 */
public class IntegerReplacement {
    public int integerReplacement(int n) {
        // 广度优先搜索
        if (n == 1) return 0;
        Queue<Long> queue = new LinkedList<> ();
        Set<Long> set = new HashSet<> ();

        queue.offer((long) n);
        set.add((long) n);
        int steps = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size -- > 0) {
                Long cur = queue.poll();
                if ((cur & 1) == 0) { // 偶数
                    long next = cur / 2;
                    if (set.contains(next)) continue ;

                    if (next == 1)  return steps;
                    queue.offer(next);
                    set.add(next);
                } else {
                    for (long next = cur - 1; next <= cur + 1; next += 2) {
                        if (set.contains(next)) continue ;

                        if (next == 1) return steps;
                        queue.offer(next);
                        set.add(next);
                    }
                }
            }
            steps ++;
        }

        return steps;
    }
}
